﻿//给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
//n == height.length
//1 <= n <= 2 * 104
//0 <= height[i] <= 105
//
//输入：height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
//输出：6
//解释：上面是由数组[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] 表示的高度图，
//      在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
//
//输入：height = [4, 2, 0, 3, 2, 5]
//输出：9

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> left(n);
        vector<int> right(n);
        // 预处理左侧最⼤值数组
        left[0] = height[0];
        for (int i = 1; i < n; i++)
            left[i] = max(left[i - 1], height[i]);
        // 预处理右侧最⼤值数组
        right[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--)
            right[i] = max(right[i + 1], height[i]);
        // 求结果
        int ret = 0;
        for (int i = 1; i < n - 1; i++) {
            ret += min(left[i], right[i]) - height[i];
        }
        return ret;
    }
};
